package test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author sunzhuokun
 * @date 9:17 2024/5/11
 * @description 滑动窗口最大和
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * <p>
 * 返回 滑动窗口中的最大值 。
 */
public class MaxSumOfSlidingWindow_滑动窗口最大和 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        MonotonicQueue<Integer> window = new MonotonicQueue<>();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {
                window.push(nums[i]);
            } else {
                // 窗口向后滑动
                window.push(nums[i]);
                // 添加当前最大值到结果
                res.add(window.max());
                // 移出最前的元素
                window.pop(nums[i - k + 1]);
            }
        }

        System.out.println(res);
    }

    /**
     * 单调递减队列；从队尾添加元素，从对头移除元素
     * 类似大顶堆
     *
     * @param <T>
     */
    static class MonotonicQueue<T extends Comparable<T>> {

        private LinkedList<T> maxQueue = new LinkedList<>();

        /**
         * 从队尾添加元素，确保队头元素最大
         *
         * @param t
         */
        private void push(T t) {
            while (!maxQueue.isEmpty() && maxQueue.peekLast().compareTo(t) < 0) {
                maxQueue.pollLast();
            }
            maxQueue.addLast(t);
        }

        private T max() {
            return maxQueue.getFirst();
        }

        private void pop(T t) {
            if (t.compareTo(maxQueue.getFirst()) == 0) {
                maxQueue.pollFirst();
            }
        }
    }
}
